题面

解题思路

树形DP+贪心排序

分析

思考这个最大值显然是满足能从子节点更新到父节点的

因此考虑我们已经得到了 $k$ 节点所有子节点的最大值 $f_{v_i}$，考虑如何更新

首先别忘了 $k$ 节点本身的值，然后由于从 $k$ 节点往下走到任意子节点 $v_i$ 均需 $1$ 的费用，并且先走子节点 $v_i$ 对另一个子节点 $v_j$ 会造成 $2\times size$ 的影响，现在我们要使这个费用总和最小化，就可以将这个问题转化为另一个问题：

现有长度为 $t$ 的数组 $p$，数组中每个元素分别有两个值，$p[i].value$ 表示从 $k$ 走到某个节点中的最大值，$p[i].size$ 对应该节点的 $2\times size$，也就是对后面的影响

费用即为：

显然 $Ans$ 的大小和数组 $p$ 中元素的顺序有关，考虑交换 $i,j(1\le i<j\le t)$ 的变化，

原先：

交换后：

最优的排序交换后肯定不能使答案更优，即上述 $\left ( 1\right )$ 式 $\le$ $\left(2\right)$ 式

又因为显然：

可得最优情况下：

即：

所以可以得出一个排序关键字 $p[i].value-p[i].size$，降序排序即可

最终根据序列得出答案

warning

建双向边emmm

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 500003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{//排序元素
    int v,s;
    node(rint a,rint b):v(a),s(b){}
    node(){}
}p[N];
int head[N],ver[N<<1],nxt[N<<1];
int n,t,a[N],f[N],size[N],sum;
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t,
    ver[++t]=x,nxt[t]=head[y],head[y]=t;
}
inline bool cmp(rgt node a,rgt node b) {//按照关键字降序排序
    return a.v-a.s>b.v-b.s;
}
inline void dfs(rint k,rint fa) {
    rint i,to;size[k]=1;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];
        if(to==fa) continue;
        dfs(to,k),size[k]+=size[to];
    }t=0;
    for(i=head[k];i;i=nxt[i]) {//循环切记分开写
        to=ver[i];
        if(to==fa) continue;
        p[++t]=node(f[to]+1,size[to]*2);
    }sort(p+1,p+t+1,cmp),sum=0;
    for(i=1;i<=t;i++)
        cmax(f[k],p[i].v+sum),sum+=p[i].s;
}
int main() {
    rint i,j;n=read();
    for(i=1;i<=n;i++) f[i]=read();f[1]+=2*n-2;
    for(i=1;i<n;i++) add(read(),read());
    dfs(1,0),printf("%d",f[1]);
    return 0;
}

devil.